Open loop flow control mechanisms are used in asynchronous networks, such as Ethernet (802.3) local area networks (LANs) and asynchronous transfer mode (ATM) networks. These mechanisms may include admission control, policing, and traffic shaping. For admission control, when an application requests a network connection, the application identifies its quality of service (QoS) requirements, and the network decides whether to accept or reject the request. In policing, the network monitors the traffic. Packets from any application that introduces more traffic than identified during network connection setup may be discarded, delayed, or shaped.
Traffic shaping changes the traffic flow to smooth bursty traffic. One type of leaky bucket traffic shaper stores incoming packets in a buffer and releases the packets at a desired rate. The buffer size determines the maximum burst size that can be accommodated.
Another leaky bucket shaping method is a token leaky bucket method. This type of model is useful for systems in which the output rate of a network resource is a constant value (e.g., a line transmission rate) when the buffer is not empty. The leaky bucket contains tokens, each of which represents one byte of data. The bucket is filled at a constant interval with a programmable number of tokens. When a packet is scheduled for transmission to an output port, the length of the packet is subtracted from the bucket. Since the fill rate is known and programmed, the state of whether this rate has been exceeded can be determined by looking at the state of the bucket. If the bucket is empty, the output rate is greater than the fill rate. If the bucket is full, the output rate is less than the fill rate.
Dual leaky bucket methods include two independent leaky buckets corresponding to minimum and maximum transmission rates respectively. If a packet is scheduled, tokens are drained independently from both buckets. In the independent leaky bucket approach, if the maximum rate for a queue is set to the line rate and the minimum rate is set to something very low, and large packets are scheduled to this queue over an extended period, the lower leaky bucket will become extremely negative as packets are drained. Eventually, the negative limit of the binary counter for the lower leaky bucket is reached, at which time additional bytes are not taken into account for the minimum rate. This translates into cumulative error. The rate being measured by the lower bucket will be inaccurate, and more inaccurate as these events occur.
For example, consider a loading scenario where the upper delta is set to a maximum line rate (1 Gbps), while the lower delta is set to a very small minimum rate. Jumbo packets are then continuously scheduled to this queue at the full line rate. Since the maximum rate will never be achieved (upper accumulator cannot go negative in one accumulator update period), jumbo frames can be scheduled to this queue indefinitely. Since the full packet length is subtracted from both accumulators, it is clear that the negative limit of the lower accumulator will be reached very quickly and packets that are scheduled after this point in time will not be accounted for. Such a load could cause the lower shaper to become extremely negative. Eventually, the token accounting for the lower shaper would have to be “clipped” in order to avoid accumulator rollover.
Because this rate measuring error is cumulative, the lower shaper would become more and more inaccurate as these types of clipping events occur. In essence, the minimum shaper rate would gradually increase since the accumulator would become positive too soon.
Improved traffic shaping methods and apparatus are desired.